#ifdef  SEQ_ENDBG
#define DBG(...)		printf( __VA_ARGS__ )
#else
#define DBG(...)
#endif

#include <stdio.h>
#include <assert.h>

#include "bitonic_interface.h"

#define SWAP(a, b)  \
			a ^= b; \
			b ^= a; \
			a ^= b

#define CMP_SWAP(a, b)     {\
			if(a > b) {     \
				SWAP(a, b); \
			}               \
		}


static void bitonic_merge_rec(data_t*, size_t);

/* Debugging */
extern void print_array(data_t*, size_t);

static
void bitonic_merge_rec(data_t *data, size_t l) {
	if(l <= 1) {
		return;
	}

	size_t step = (l/2);
	size_t q = step;

	if(l%2 == 1) {
		if(data[ step ] < data[ (l-1) ]) {
			q++;
		}
		step++;
	}

	for(size_t i = 0; i < (l/2); i++) {
		CMP_SWAP(data[i], data[i+step]);
	}

	//print_array(data, l);
	DBG("[0] +(%ld), [%ld] +(%ld)\n", q, q, l-q);
	bitonic_merge_rec(data, q);
	bitonic_merge_rec(data+q, l-q);
}

void bitonic_merge(data_t *data, size_t q, size_t l, int p) {
	if(l == 1) {
		return;
	}
	size_t m = (l-1)/2;
	DBG(" q[%ld] l[%ld]\n", q, l);

	/* [0] -> [q], [q+1] -> [l-1] */
	if(q <= m) {
		size_t i = 0;
		size_t j = (2*q)+1;

		for(; i <= q; i++, j--) {
			DBG("  0:0  i[%ld] j[%ld]\n", i, j);
			CMP_SWAP(data[i], data[j]);
		}
	} else /* q > m */ {
		size_t i = q-((l-1)-q)+1;
		size_t j = (l-1);

		for(; j > q; i++, j--) {
			DBG("  1:1  i[%ld] j[%ld]\n", i, j);
			CMP_SWAP(data[i], data[j]);
		}
	}
	//print_array(data, l);
	DBG("[0] +(%ld), [%ld] +(%ld)\n", q+1, q+1, l-q-1);
	bitonic_merge_rec(data, q+1);
	bitonic_merge_rec(data+(q+1), l-q-1);
}
